#include <bits/stdc++.h>

using namespace std;

/**
     * @param n: an integer
     * @return: an ineger f(n)
     */
int fibonacci(int n)
{
    // write your code here
    int *fib = new int[n];
//    int fib[1000];
    fib[0] = 0;
    fib[1] = 1;
    for(int i = 2; i < n; i++)
        fib[i] = fib[i-1] + fib[i-2];
    return fib[n-1];
}

int main()
{
    for(int i = 1; i <= 500; i++)
        printf("%d:\t%d\n", i, fibonacci(i));
    return 0;
}

/**
斐波纳契数列

查找斐波纳契数列中第 N 个数。

所谓的斐波纳契数列是指：

    前2个数是 0 和 1 。
    第 i 个数是第 i-1 个数和第i-2 个数的和。

斐波纳契数列的前10个数字是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
注意事项

样例

给定 1，返回 0

给定 2，返回 1

给定 10，返回 34

*/
